/*
 * @lc app=leetcode.cn id=554 lang=cpp
 *
 * [554] 砖墙
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        // 遍历哈希表，找到出现次数最多的砖块边缘即可，不需验证沿所有边缘切割结果

        int wallHeight = wall.size();
        int wallWidth = std::accumulate(wall[0].begin(), wall[0].end(), 0);
        
        if (wallWidth == 1){return wallHeight;}

        std::set<int> candidatePosSet;
        for (auto& level : wall){
            int length = 0;
            for (int i=0;i<level.size()-1;i++){
                length += level[i];
                candidatePosSet.emplace(length-1);
            }
        }

        if (candidatePosSet.size()==0){return wallHeight;}

        int leastBrickNum = wallHeight;
        for (int pos : candidatePosSet){
            int counter = 0;
            for (int j=0;j<wallHeight;j++){
                if (throughBrick(wall[j], pos)){
                    counter ++;
                }
            }
            if (counter < leastBrickNum){
                leastBrickNum = counter;
            }
        }
        return leastBrickNum;
    }
    bool throughBrick(vector<int>& level, int pos){
        int length = pos + 1;
        int sum = 0;
        for (int i=0;i<level.size() and sum < length;i++){
            sum += level[i];
        }
        return !(sum==length);
    }
};
// @lc code=end

